Faster fixed-parameter tractable algorithms for matching and packing problems

Title: Faster fixed-parameter tractable algorithms for matching and packing problems
Creator: Fellows, M. R.; Knauer, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; Stege, U.; Thilikos, D. M.; Whitesides, S.
Relation: Algorithmica Vol. 52, Issue 2, p. 167-176
Publisher Link: http://dx.doi.org/10.1007/s00453-007-9146-y
Publisher: Springer
Resource Type: journal article
Date: 2008
Description: We obtain faster algorithms for problems such as r-dimensional matching and r-set packing when the size k of the solution is considered a parameter. We first establish a general framework for finding and exploiting small problem kernels (of size polynomial in k). This technique lets us combine Alon, Yuster and Zwick’s color-coding technique with dynamic programming to obtain faster fixed-parameter algorithms for these problems. Our algorithms run in time O(n+2 O(k)), an improvement over previous algorithms for some of these problems running in time O(n+k O(k)). The flexibility of our approach allows tuning of algorithms to obtain smaller constants in the exponent.
Subject: parameterized complexity; fixed parameter tractable; graph matching; set packing; color coding
Identifier: http://hdl.handle.net/1959.13/41262
Identifier: uon:4698
Identifier: ISSN:1432-0541
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format